package pfq.demo.algorithm.tree;

import java.util.Random;

/**
 * 二叉树的遍历：
 * 前序、中序、后序
 * <p>
 * 思路：使用递归
 * <p>
 * 此处的前中后，指的是节点与其左右子树的顺序，比如先访问自己，再访问左子树，最后访问右子树，就是前序遍历
 * <p>
 * 补充：
 * 深度优先和广度优先遍历，和前中后序遍历，是两种不同思路的遍历方式，两者其实是不相关的，不能说前中后属于深度广度，或者深度广度属于前中后序
 * <p>
 * 只是后序遍历正好属于深度优先遍历而已，但前序、中序既不是深度优先也不是广度优先
 */
public class BinaryTree {

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 前中后序遍历的代码其实不难实现，没想到难的竟然是创建二叉树的代码，也是一个递归函数
     */
    public static Node create(Node node, int i, int height) {
        if (i >= height) {
            return null;
        }

        if (node == null) {
            node = new Node(new Random().nextInt(100), null, null);
        }

        node.left = create(node.left, i + 1, height);
        node.right = create(node.right, i + 1, height);

        return node;
    }

    public static void preOrder(Node node) {
        if (node == null) {
            return;
        }

        System.out.print(node.data + " ");

        preOrder(node.left);
        preOrder(node.right);


    }

    public static void midOrder(Node node) {
        if (node == null) {
            return;
        }

        preOrder(node.left);
        System.out.print(node.data + " ");
        preOrder(node.right);


    }

    public static void sufOrder(Node node) {
        if (node == null) {
            return;
        }

        preOrder(node.left);
        preOrder(node.right);
        System.out.print(node.data + " ");


    }


    public static void main(String[] args) {
        // 创建一个二叉树
        Node node = create(null, 0, 3);

        // 前序
        System.out.println("前序遍历：");
        preOrder(node);
        System.out.println();

        // 中序
        System.out.println("中序遍历：");
        midOrder(node);
        System.out.println();

        // 后序
        System.out.println("后序遍历：");
        sufOrder(node);
        System.out.println();

    }
}
